In printing, when a continuous tone image (such as a photograph) is converted into a monotone medium (e.g., black-and-white) image, it is typically “halftoned.” In a halftone process, a continuous tone image is converted to various apparent levels of gray using either patterns of monotone (i.e., single color) dots of various sizes or using lines of various widths. This halftone process may be called “halftoning.” This process may be called “dithering.”
Conventional Printing
In conventional printing (e.g., on a printing press), one way that halftones are created is by photographing an image through a screen (e.g., a filter). The screen frequency, measured in lines per inch, determines how many dots are used to make each spot of gray. In theory, the higher the screen frequency (the more lines per inch), the more accurate the halftone will be. However, actual screen frequencies are limited by the technology because higher screen frequencies create smaller, more tightly packed dots. If printing is being done on a low-resolution device, therefore, better results may occur with a lower screen frequency.
Electronic Displays
Electronic displays have the ability to display gray levels by varying the intensity of a dot, pel, or pixel produced in the display. However, most marking engines still provide only monotone output. Marking engines must therefore employ halftone techniques to simulate levels of gray. Examples of devices including marking engines are laser printers, LED printers, electrothermographic printers, copiers, multifunction devices, and the like. Monotone marking engines simulate levels of gray using clusters of dots or pixels, so that pixel locations in the cluster are marked (i.e., black or “on”) or left blank (i.e., white or “off”) in various patterns. The clusters are often referred to as halftone cells.
Raster of Shades of Gray
In a typical application, a monotone marking engine is utilized. Such a marking engine has a native resolution. For example, standard laser printers have specified native resolutions of 300, 600, 1200, or more dpi (dots per inch). The centers of the marking regions (i.e., pixel locations) for a 300 dpi device, for example, are located 1/300 of an inch apart in both the horizontal and vertical directions of the paper. Therefore, the native resolution of a marking engine may be represented by an orthogonal array of pixel locations. This array may be called a “raster.” The two dimensional size of the array depends on the total paper size or output area of the graphic image.
A gray level (i.e., shade or tone) value is assigned to each pixel location in the array. This value is used in electronic displays (such as video displays, cathode ray tubes (CRTs), or liquid crystal displays (LCDs)) to control the intensity of the corresponding pixel. A conventional way of assigning gray values is to set the value of a multi-bit binary number for each pixel in the array. Such an array may be referred to variously as grayscale data, a grayscale array, or video raster data.
Simulated Grayscale
Ordinarily, the availability of grayscale data, alone, does not allow a marking engine to simulate the gray levels contained in the data. By its nature, a monotone marking engine cannot print actual shades of gray. It also cannot vary the intensity at each pixel location. Typically, it either marks the entire pixel region or leaves it blank.
In order to simulate gray levels, the monotone marking engine must use pixel clusters (i.e., halftone cells) formed of marked and blank pixels to provide a number of gray level patterns. The number of patterns available in a halftone scheme theoretically corresponds directly to the size of the pixel cluster. However, inherent properties of most marking engines reduce or limit the number of gray levels available in actual practice.
The best set of simulated gray levels are those that appear linear or smooth to a viewer. The process of selecting the best set of gray levels is called “tone curve generation.” A tone curve is a representation of the gray levels selected, and tone curve generation is the process of selecting these values taking into account gamma correction, tone correction for the marking engine, and posterization (or image smoothness).
Sub-Pixel Marks
One approach to tone curve generation has been to reduce the pulse width that drives the imaging laser in a laser printer. Using the multi-bit (e.g., 4 bits) grayscale data of a pixel, the laser printer may create a dot (i.e., mark) that is smaller than a full size pixel, in the hope of providing a greater number of distinguishable gray levels. This smaller dot may be called a sub-pixel mark
For example, a conventional marking engine divides the pixel period of the laser by sixteen, and provides sixteen different dot sizes or marks for any given pixel region. Usually, such dots are centered on the pixel region location. In such schemes, the laser is turned on by a pulse having duration between 0/15th and 15/15th of the pixel period, the pulse being centered in the pixel period interval. If grayscale data is provided with four bits per pixel gray values, sixteen different shades can be specified for each pixel. The size of the subpixel mark at each pixel region is controlled by such pulses in an attempt to simulate gray levels.
Furthermore, conventional marking engines can effectively place the subpixel mark within a pixel region. More precisely, they can position the center of a subpixel mark to a location within the pixel region other than the true center. For example, a small subpixel mark (e.g., 2/15th of the pixel period) may be towards the right side of a pixel region.
Conventional Multi-bit Halftoning
Multi-bit halftoning is a technique for halftoning that takes advantage of the multi-bit grayscale data and a printer's ability to create subpixel marks. It further uses the printer's ability to control the size of the subpixel mark at a pixel region and to place a subpixel mark within a pixel region.
However, it is not a simple conversion from the multi-bit grayscale data to the halftone cell patterns. It is not a one-to-one conversion. As described above, the halftone cells are a cluster of pixels. The cells will not form a cohesive cluster if the pixels therein are partially formed. Therefore, multi-bit halftoning uses grayscale data from a collection of neighboring pixels to from the proper halftone cell pattern to simulate the level of gray.
An example of the conventional multi-bit halftoning technique is described in U.S. Pat. No. 5,515,480, entitled “System and Method for Enhancing Graphic Features Produced by Marking Engines,” issued on May 7, 1996.
Limitations of Conventional Multi-bit Halftoning
Conventional multi-bit halftoning is slow and inefficient. It uses processors to calculate the conversion from multi-bit grayscale raster data into multi-bit halftones. Since processors are not specialized circuitry and since processors tend to execute a series of instructions, they are slower than a specialized circuitry (e.g., hardware) designed to do multi-bit halftone conversions.
Conventional multi-bit halftoning requires a memory (e.g., RAM) and intermediate steps of storing halftoned data in the memory and retrieving the data from the memory. This adds to the overall inefficiency of conventional multi-bit halftoning. Since the conventional conversion of grayscale to halftone generates multiple clusters, the memory temporarily stores the results of the conversion.
Furthermore, the conventional halftoning employs large look-up tables (LUTs). The large LUT consume additional memory. A LUT is table of values stored in a computer that is searched until a specified value is found. Searching for a value in a large LUT takes time. This time adds up quickly because this search is performed for each pixel. In addition, these LUT are typically quite large. The LUT takes a large amount of memory (e.g., RAM). That memory could otherwise be used to buffer page data. Compressed or reduced LUTs exist, but they require interpolation with complex mathematically computations.
Moreover, conventional multi-bit halftoning is inflexible. Each implementation is tailored for marking engines having a specific resolution. A conventional multi-bit halftoning system designed for a printer with a 600 dpi resolution would not have the flexibility to operate at 300 dpi.
Furthermore, each implementation of a conventional multi-bit halftoning system is tailored to convert from a specific “grayscale-depth” to the same “halftone-depth.” Grayscale-depth is the number of bits per pixel for encoding grayscale for display (or storage) of a continuous tone image. Halftone-depth is the number of bits per pixel for encoding halftoning for printing of an image. For example, a conventional system may be designed to convert 4-bit grayscale data of an image into 4-bit halftone data. However, that same system cannot accommodate any other depth (e.g., 16-bit grayscale data or 8-bit grayscale data). Nor can it convert from one size grayscale-depth to another size halftone-depth.
Therefore, with conventional multi-bit halftoning, a user does not have the option to use a range of resolutions and/or a range of grayscale-depth.
The conventional solution to this problem is to design multiple implementations of the conventional multi-bit halftoning into a signal printer. Each implementation is designed to handle a specific combination of resolution and grayscale-depth. One can see that such a solution is inefficient and cumbersome.
Conclusion of Background
From the foregoing discussion, it is evident that the conventional art has failed to provide a mechanism for performing multi-bit halftoning that is efficient and flexible. All conventional systems rely on processors (with their bottlenecks) and large look-up tables (with their storage requirements). They use resources—such as memory—to temporarily store results. Consequently, they are slow and inefficient. All conventional systems are limited to a fixed number of bits per pixel (i.e., grayscale-depth and halftone-depth) and a fixed resolution. Consequently, they are inflexible.
Accordingly, what is needed is a fast and efficient technique for multi-bit halftoning. Perhaps, one is needed that does not rely on processors and large look-up tables. Moreover, what is needed is a flexible technique for multi-bit halftoning. One that can perform multi-bit halftoning for a variable number of bits per pixel and a variable resolution.